/* Copyright (c) 2006 by M Aamir Maniar 
 * 
 * Permission is hereby granted, free of charge, to any person obtaining 
 * a copy of this software and associated documentation files (the 
 * "Software"), to deal in the Software without restriction, including 
 * without limitation the rights to use, copy, modify, merge, publish, 
 * distribute, sublicense, and/or sell copies of the Software, and to 
 * permit persons to whom the Software is furnished to do so, subject to 
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 * */

namespace Generic.DataStructures
{
	using System;
	using SysGeneric = System.Collections.Generic;
	using System.Text;
	using System.Diagnostics;
	using System.Runtime.InteropServices;
    using Generic.Utils;

	/// <summary>
	/// Represetns the array based Queue by implementing <see cref="IQueue&lt;T&gt;"/>.
	/// </summary>
	/// <remarks>
	/// Use the Queue when you want list based on FIFO (first-in last-out) principal.
	/// </remarks>
	/// <typeparam name="T"></typeparam>
	[
	DebuggerDisplay("Count = {Count}"),
	ComVisible(true),
	DebuggerTypeProxy(typeof(Generic.DataStructures.Queue<>.QueueDebugView)),
    Serializable()
	]
	public class Queue<T> : IQueue<T>
	{
		#region Initial Member Declaration
		public const int DEFAUT_CAPACITY = 32;
		private T[] _array;
		private int _size;
        private float _growFactor;
        private int _headIndex;
        private int _tailIndex;
		#endregion

		#region Constructors
		/// <summary>
		/// Initializes a new instance of the <see cref="Queue&lt;T&gt;"/> class.
		/// </summary>
		public Queue()
			: this(DEFAUT_CAPACITY)
		{
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="Queue&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="capacity">The capacity.</param>
		public Queue(int capacity)
		{
			if (capacity < 0)
				throw new ArgumentOutOfRangeException("Queue size cannot be less then zero.");
			_capacity = capacity;
			_array = new T[capacity];
			_size = 0;
            _headIndex = 0;
            _tailIndex = 0;
            _growFactor = 2.0F;
            _fixedSize = false;
		}

        /// <summary>
        /// Initializes the new instance of the empty Queue class, has empty initial capacity and specified growing factor.
        /// </summary>
        /// <param name="capacity">Initial number of elements queue can hold.</param>
        /// <param name="growFactor">The queue growing factor.</param>
        /// <remarks>
        /// Capacity of the queue represents number of elements the Queue can accommodate. 
        /// In case of non fixed sized Queue, capacity is automatically increased.
        /// In that case growingFactor parameter is taken 
        /// into consideration.
        /// </remarks>
        public Queue(int capacity, float growFactor) 
            : this(capacity)
        {
            ArgumentValidator.CheckIndexForRange<float> (growFactor, 1, 10, "The growFactor parameter should be between 1.0 && 10.0");
            _growFactor = growFactor;
        }

        public Queue(int capacity, bool fixedSize)
            : this(capacity)
        {
            _fixedSize = fixedSize;
        }

		/// <summary>
		/// Initializes a new instance of the <see cref="Queue&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="collection">The collection.</param>
		public Queue(SysGeneric.ICollection<T> collection)
			: this()
		{
			if (collection == null)
				throw new ArgumentNullException("Supplied collection can not be null.");
			foreach (T item in collection)
				Enqueue(item);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="Queue&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="list">The list.</param>
		public Queue(SysGeneric.IList<T> list)
			: this()
		{
			if (list == null)
				throw new ArgumentNullException("Supplied collection can not be null.");
			foreach (T item in list)
				Enqueue(item);
		}

		public Queue(T[] array)
			: this()
		{
			if (array == null)
				throw new ArgumentNullException("Supplied array can not be null.");
			if (array.Rank != 1)
				throw new ArgumentException("Queue cannot accept multidimention array");

			for (int index = 0; index < array.Length; index++)
				Enqueue(array[index]);
		}
		#endregion

        #region IQueue<T> Members

        public void Enqueue(T item)
        {
            if (item == null)
                throw new ArgumentNullException("Item to be enqueued can not be null.");
            if (_size == _array.Length)
            {
                if (FixedSize)
                {
                    if (AutoDequeue)
                        Dequeue();
                    else
                        throw new InvalidOperationException("Queue is full. Element can not be pushed since Queue is FixedSized");
                }
                else
                {
                    Capacity = Convert.ToInt32(_size * _growFactor);
                }
            }
            
            _array[_tailIndex] = item;
            _tailIndex = ++_tailIndex % _array.Length;
            _size++;
        }

        public T Dequeue()
        {
            if (_size == 0)
                throw new InvalidOperationException("Can not perform Dequeue when there is no item in the Queue.");

            T item = _array[_headIndex];
            _array[_headIndex] = default(T);
            _headIndex = ++_headIndex % _array.Length;
            _size--;
            return item;
        }

        #endregion

        #region public int Capacity
        int _capacity;
        /// <summary>
        /// Gets or sets the capacity of the <see cref="Queue&lt;T&gt;"/>.
        /// </summary>
        /// <value>The capacity.</value>
        public int Capacity
        {
            //TODO: Queue: Setting up of capacity function
            get
            {
                return _capacity;
            }
            set
            {
                _capacity = value;
                if (value > 0)
                {
                    T[] tempArray = new T[_capacity];
                    if (_size > 0)
                    {
                        if (_headIndex < _tailIndex)
                            Array.Copy(_array, _headIndex, tempArray, 0, _size);
                        else
                        {
                            Array.Copy(_array, _headIndex, tempArray, 0, _array.Length - _headIndex);
                            Array.Copy(_array, 0, tempArray, _array.Length - _headIndex, _tailIndex);
                        }
                    }

                    _array = tempArray;
                    _headIndex = 0;
                    _tailIndex = (_size == _capacity) ? 0 : _size;   
                }
            }
        }
        #endregion

        #region public bool AutoDequeue
        private bool _autoDequeue;
        /// <summary>
        /// Gets or sets the auto dequeue mode for the queue.
        /// </summary>
        /// <remarks>
        /// This property only worked if <see cref="FixedSized"></see> property is true.
        /// </remarks>
        /// <value>
        /// First item is removed from the queue when enque is performed on a full fixed sized 
        /// queue.
        /// </value>
        public bool AutoDequeue
        {
            get
            {
                return _autoDequeue;
            }
        }
        #endregion

        #region Commented Region
        /*
        #region public virtual T Pop()
        /// <summary>
		/// Pops the top most item from the <see cref="Queue&lt;T&gt;"/>.
		/// </summary>
		/// <returns>The item poped.</returns>
		public virtual T Pop()
		{
			if (_size == 0)
				throw new InvalidOperationException("Can not perform pop when there is no item in the Queue.");
			T item = _array[--_size];
			_array[_size] = default(T);
			return item;
		}
		#endregion

		#region public virtual T Top
		/// <summary>
		/// Returns the top most element withought changing <see cref="Queue&lt;T&gt;"/>.
		/// </summary>
		/// <returns></returns>
		public virtual T Top
		{
			get
			{
				if (_size == 0)
					throw new InvalidOperationException("Can not perform pop when there is no item in the Queue.");
				return _array[_size - 1];
			}
		}
		#endregion
*/        
#endregion        

        #region public bool FixedSize
        private bool _fixedSize = true;
		/// <summary>
		/// Gets or sets a value indicating whether <see cref="Queue&lt;T&gt;"/> is fixed sized.
		/// </summary>
		/// <value><c>true</c> if Queue is fixed sized; otherwise, <c>false</c>.</value>
		public bool FixedSize
		{
			get { return _fixedSize; }
			set 
            { 
                _fixedSize = value;
                _autoDequeue = true;
            }
		}
		#endregion

		#region public bool IsFull
		/// <summary>
		/// Gets a value indicating whether <see cref="Queue&lt;T&gt;"/> is full.
		/// </summary>
		/// <value><c>true</c> if this instance is full; otherwise, <c>false</c>.</value>
		public bool IsFull
		{
			get
			{
				if (FixedSize)
				{
					if (_size == _array.Length)
					{
						return true;
					}
				}
				return false;
			}
		}
		#endregion

		#region public bool IsEmpty
		public bool IsEmpty
		{
			get
			{
				return _size == 0;
			}
		}
		#endregion

		#region public object SyncRoot
		private static object _syncRoot;
		/// <summary>
		/// Gets the SyncRoot, an object that help to created synchronized objects.
		/// </summary>
		/// <value>The sync root.</value>
		[ComVisible(false)]
		public object SyncRoot
		{
			get
			{
				if (_syncRoot == null)
				{
					object newRoot = new object();
					System.Threading.Interlocked.CompareExchange(ref _syncRoot, newRoot, null);
				}
				return _syncRoot;
			}
		}
		#endregion

		#region public bool IsSynchronized
		/// <summary>
		/// Gets a value indicating whether this instance is synchronized.
		/// </summary>
		/// <value>
		/// 	<c>true</c> if this instance is synchronized; otherwise, <c>false</c>.
		/// </value>
		public bool IsSynchronized
		{
			get
			{
				return false;
			}
		}
		#endregion

		/// <summary>
		/// Returns the synchronized version of <see cref="<see cref="Queue&lt;T&gt;"/>"/>.
		/// </summary>
		/// <param name="Queue">The Queue.</param>
		/// <returns></returns>
		public static Queue<T> Synchronized(Queue<T> Queue)
		{
			return new SynchronizedQueue<T>(Queue) as Queue<T>;
		}


		#region ICollection<T> Members


		void SysGeneric.ICollection<T>.Add(T item)
		{
			throw new NotSupportedException("Queue class dose not support this method. Use Enqueue method to add item on the Queue.");
		}

		bool SysGeneric.ICollection<T>.Remove(T item)
		{
			throw new Exception("Queue does not support this method. Use Dequeue method to remove item from the Queue.");
		}

		/// <summary>
		/// Removes all items from the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </summary>
		/// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only. </exception>
		public void Clear()
		{
			PerfomReadonlyValiadtion();
			if (_size > 0)
				Array.Clear(_array, 0, _size);
            _headIndex = 0;
            _tailIndex = 0;
		}

		/// <summary>
		/// Determines whether the <see cref="T:System.Collections.Generic.ICollection`1"></see> contains a specific value.
		/// </summary>
		/// <param name="item">The object to locate in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
		/// <returns>
		/// true if item is found in the <see cref="T:System.Collections.Generic.ICollection`1"></see>; otherwise, false.
		/// </returns>
		public virtual bool Contains(T item)
		{
            for (int index = 0; index < _array.Length; index++)
            {
                if (_array[index].Equals(item))
                    return true;
            }
            return false;
        }

        #region public void CopyTo(T[] array, int arrayIndex)
        /// <summary>
        /// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1"></see> to an <see cref="T:System.Array"></see>, starting at a particular <see cref="T:System.Array"></see> index.
        /// </summary>
        /// <param name="array">The one-dimensional <see cref="T:System.Array"></see> that is the destination of the elements copied from <see cref="T:System.Collections.Generic.ICollection`1"></see>. The <see cref="T:System.Array"></see> must have zero-based indexing.</param>
        /// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
        /// <exception cref="T:System.ArgumentOutOfRangeException">arrayIndex is less than 0 or greater than array length.</exception>
        /// <exception cref="T:System.ArgumentNullException">array is null.</exception>
        /// <exception cref="T:System.ArgumentException">array is multidimensional.-or-arrayIndex is equal to or greater than the length of array.-or-The number of elements in the source <see cref="T:System.Collections.Generic.ICollection`1"></see> is greater than the available space from arrayIndex to the end of the destination array.-or-Type T cannot be cast automatically to the type of the destination array.</exception>
        public void CopyTo(T[] array, int arrayIndex)
		{
			if (array == null)
				throw new ArgumentNullException("Parameter 'array' is null.");
			if (arrayIndex < 0)
				throw new ArgumentOutOfRangeException();
			if (array.Rank != 1)
				throw new ArgumentException("Parameter 'array' is a multidimentional array.");
			//TODO:	Queue.CopyTo
            T[] newArray = ToArray();
            int copyLength = array.Length - arrayIndex;
            int newLength = (copyLength>newArray.Length)?newArray.Length:copyLength;            
            Array.Copy(newArray, 0, array, arrayIndex, newLength);
        }
        #endregion

        /// <summary>
		/// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </summary>
		/// <value></value>
		/// <returns>The number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</returns>
		public int Count
		{
			get
			{
				return _size;
			}
		}

		private bool _isReadOnly = false;
		/// <summary>
		/// Gets a value indicating whether the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only.
		/// </summary>
		/// <value></value>
		/// <returns>true if the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only; otherwise, false.</returns>
		public bool IsReadOnly
		{
			get
			{
				return _isReadOnly;
			}
		}



		#endregion

		#region IEnumerable<T> Members

		public SysGeneric.IEnumerator<T> GetEnumerator()
		{
			for (int index = 0; index < _array.Length; index++)
				yield return _array[index];
		}

		#endregion

		#region IEnumerable Members

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return GetEnumerator() as System.Collections.IEnumerator;
		}

		#endregion

		#region ICloneable Members

        public Queue<T> Clone()
        {
            return Generic.Patterns.Prototype<Queue<T>>.Clone(this);
        }

		object ICloneable.Clone()
		{
            return this.Clone();
		}

		#endregion

		#region protected void PerfomReadonlyValiadtion()
		/// <summary>
		/// Perfoms the readonly valiadtion.
		/// </summary>
		/// <exception cref="T:System.NotSupportedException"
		protected void PerfomReadonlyValiadtion()
		{
			if (IsReadOnly)
				throw new NotSupportedException("Can not change read only Queue.");
		}
		#endregion

		#region internal class LinkedListDebugView
		internal class QueueDebugView
		{
			Queue<T> _queue;
			public QueueDebugView(Queue<T> queue)
			{
				_queue = queue;
			}

			[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			public T[] Items
			{
				get
				{
					return _queue.ToArray();
				}
			}


		}
		#endregion

        /* Private */


        #region IQueue<T> Members


        public T First
        {
            get 
            {
                if (_size == 0)
                    throw new InvalidOperationException("Can not execute statement when there is no item in the Queue.");
                return _array[_headIndex];
            }
        }

        public T Last
        {
            get 
            {
                if (_size == 0)
                    throw new InvalidOperationException("Can not execute statement when there is no item in the Queue.");                
                return _array[((_tailIndex == 0) ? _size : _tailIndex)-1];
            }
        }

        #endregion

        public T[] ToArray()
        {
            int count = 0;
            T[] items = new T[Count];
            for (int index = _headIndex; index < _array.Length; index++)
                items[count++] = _array[index];
            for (int index = 0; index < _tailIndex; index++)
                items[count++] = _array[index];
            return items;
        }
    }
}
